package datastructure.maxheap;

/**
 * @author XY
 * @version 1.0
 * @date 2021/11/15 10:10
 * @Description 使用数组存储的最大堆
 */
public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;

    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }

    public MaxHeap(){
        data = new Array<>();
    }

    //将任意数组整理成堆的样子，从最后一个非叶子节点开始，往前每一个节点都做一次siftDown操作即可
    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        for(int i = parent(data.getSize()-1); i>=0; i--){
            siftDown(i);
        }
    }

    public int size(){
        return data.getSize();
    }

    public boolean isEmpty(){
        return data.isEmpty();
    }

    //返回完全二叉树的数组表示中，一个索引代表的元素的父亲节点的索引
    private int parent(int index){
        if(index==0){
            throw new RuntimeException("index-0 doesn't have parent");
        }
        return (index-1)/2;
    }

    //返回完全二叉树的数组表示中，一个索引代表的元素的左孩子的索引
    private int leftChild(int index){
        return 2*index+1;
    }

    //返回完全二叉树的数组表示中，一个索引代表的元素的右孩子的索引
    private int rightChild(int index){
        return 2*index+2;
    }

    //向堆中添加元素（数组末尾添加元素） 并根据要添加的元素的大小 做sift up操作
    public void add(E element){
        data.addLast(element);
        siftUp(data.getSize()-1);
    }

    private void siftUp(int i) {
        while(i>0&&data.get(i).compareTo(data.get(parent(i)))>0){
            data.swap(i,parent(i));
            i = parent(i);
        }
    }

    //取出堆中元素,一般是取最大的元素（优先队列思想）
    public E extractMax(){
        if(data.isEmpty()){
            throw new RuntimeException("heap is empty");
        }
        E e = data.get(0);
        data.swap(0,data.getSize()-1);
        data.deleteLast();
        siftDown(0);
        return e;
    }

    private void siftDown(int i) {
        while(leftChild(i)<data.getSize()){
            //先拿到左孩子，因为一个节点如果有子节点的话一定现有左孩子
            int j = leftChild(i);
            //比较左孩子与有孩子哪个大，最后跟最大的进行比较
            if(j+1<data.getSize()&&data.get(j+1).compareTo(data.get(j))>0){
                j = rightChild(i);
            }
            //如果当前元素大于孩子元素，那就说明已经符合堆的性质
            if(data.get(i).compareTo(data.get(j))>0){
                break;
            }
            //否则交换位置继续比较
            data.swap(i,j);
            i = j;
        }
    }

    public E findMax(){
        if(data.isEmpty()){
            throw new RuntimeException("data is empty");
        }
        return data.get(0);
    }

    //取出最大元素，放入一个新元素
    public E replace(E e){
        data.set(0,e);
        siftDown(0);
        return data.get(0);
    }

//    //将任意数组整理成堆的样子
//    public void heapify(){
//
//    }



}
